/*
Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


//Definition for singly-linked list.
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode* partition(ListNode* head, int x) {


		if (head == NULL||head->next == NULL)
		{
			return head;
		}

		ListNode* lowerHead = new ListNode(-1);
		ListNode* upperHead = new ListNode(-1);

		ListNode* lowerPtr = new ListNode(-1);
		ListNode* upperPtr = new ListNode(-1);

		lowerPtr = lowerHead;
		
		upperPtr = upperHead;

		ListNode* p = new ListNode(-1);

		p = head;

		while (p!=NULL)
		{
			if (p->val < x)
			{
				ListNode* temp = new ListNode(p->val);
				lowerPtr->next = temp;
				lowerPtr = lowerPtr->next;
				
			}
			else
			{
				ListNode* temp = new ListNode(p->val);
				upperPtr->next = temp;
				upperPtr = upperPtr->next;
			}

			p = p->next;
		}
		head->next = NULL;
		
		if (lowerHead->next!=NULL)
		{
			head->next = lowerHead->next;
			lowerPtr->next = upperHead->next;
		}
		else
		{
			head->next = upperHead->next;
		}

		head = head->next;
		return head;


	}
};

int main()
{
	cout << "Partion List :  " << endl;

	int length;
	cout << "Input the length of the List: " << endl;

	cin >> length;

	//vector<int> nums;

	ListNode *head = new ListNode(-1);
	ListNode *p = new ListNode(-1);

	p = head;

	while (length--)
	{
		int element;
		cin >> element;
		ListNode *q = new ListNode(element);
		p->next = q;
		p = p->next;
		//nums.push_back(element);
	}

	head = head->next;

	Solution s;

	head = s.partition(head,3);

	cout << "The result: " << endl;

	system("pause");

	return 0;
}